package pers.vic.basics.leetcode;

import java.util.Arrays;

/**
 * @description: 34. 在排序数组中查找元素的第一个和最后一个位置 {@literalhttps://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/}
 * @author Vic.xu
 * @date: 2020/11/25 0025 8:39
 */
public class J0034_M_SearchRange {
    /*
    给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
    你的算法时间复杂度必须是 O(log n) 级别。
    如果数组中不存在目标值，返回 [-1, -1]。
     */

    /**
     * 算法时间复杂度必须是 O(log n) 级别。
     * 大概就是两个二分，分别找它的左右区间，这么试试吧
     * 我去  边界把我绕晕了  不写了  暴力走起： 找到target  左右滑动
     */
    public static int[] searchRange(int[] nums, int target) {
        int[] res = {-1, -1};
        int len = nums.length;
        if (len == 0) {
            return res;
        }
        int l = 0;
        int r = len - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (nums[m] > target) {
                r = m - 1;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                l = m;
                r = m;
                while (l - 1 >= 0 && nums[l - 1] == target) {
                    l--;
                }
                while (r + 1 < len && nums[r + 1] == target) {
                    r++;
                }
                res[0] = l;
                res[1] = r;
                break;
            }
        }
        return res;
    }

    // 查找到左边的下标 √
    public static int searchLeft(int[] nums, int target) {
        int res = -1;
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            int m = (r + l) / 2;
            //逐渐往左边收缩
            if (nums[m] >= target) {
                r = m + 1;
            } else {
                l = m - 1;
            }
        }
        if (nums[l] == target) {
            res = l;
        }
        return res;
    }

    /**
     * 查找到右边边的下标， 此时 左边的下边已经确定 ，只要不断的判断mid，把left下标不断右移即可：
     * 遇到mid<=target(其实不会小于，因为是有序的)，left则往右移
     */
    public static int searchRight(int[] nums, int target, int left) {
        //左边没找到 就是没有目标数
        if (left == -1) {
            return -1;
        }

        int res = -1;
        int l = left;
        int r = nums.length - 1;
        while (l < r) {
            int m = (r + l) / 2;
            //逐渐往右边收缩
            if (nums[m] <= target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        if (nums[l] == target) {
            res = l;
        }
        return res;
    }

    public static void main(String[] args) {

        //2 3
        System.out.println(Arrays.toString(searchRange(new int[]{1, 2, 3, 3, 4, 5}, 3)));
        System.out.println(1);
        //3 4
        System.out.println(Arrays.toString(searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8)));
        System.out.println(2);
        //-1 -1
        System.out.println(Arrays.toString(searchRange(new int[]{1,1}, 1)));
        System.out.println(3);
    }


}
